/*
*	ID : pallab81
* 	PROG : HiddenPassword
* 	LANG : C++
* 	2012-07-07-23.10.17 Saturday
*
* 	"I have not failed, I have just found 10000 ways that won't work.
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;


#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

template<class T1>
inline void debug(T1 _x) {
    cout<<_x<<'\n';
}
template<class T1, class T2>
inline void debug(T1 _x,T2 _y) {
    cout<<_x<<' '<<_y<<'\n';
}
template<class T1, class T2, class T3>
inline void debug(T1 _x,T2 _y,T3 _z) {
    cout<<_x<<' '<<_y<<' '<<_z<<'\n';
}
template<class T1, class T2, class T3, class T4>
inline void debug(T1 _x,T2 _y,T3 _z,T4 _zz) {
    cout<<_x<<' '<<_y<<' '<<_z<<' '<<_zz<<'\n';
}
template< class T1>
inline void debug(T1 _array,int _size) {
    cout<<"[";
    for (int i=0; i<_size; ++i) {
        cout<<' '<<_array[i];
    }
    puts(" ]");
}
inline bool CI(int &_x) {
    return scanf("%d",&_x)==1;
}
inline bool CI(int &_x, int &_y) {
    return CI(_x)&&CI(_y) ;
}
inline bool CI(int &_x, int &_y, int &_z) {
    return CI(_x)&&CI(_y)&&CI(_z) ;
}
inline bool CI(int &_x, int &_y, int &_z, int &_zz) {
    return CI(_x)&&CI(_y)&&CI(_z)&&CI(_zz) ;
}
inline void wait( double seconds ) {
    double endtime = clock()+( seconds* CLOCKS_PER_SEC );
    while( clock() < endtime ) {
        ;
    }
}
namespace suffixArray {
#define mxn 200000
#define alphabet 256
char s[mxn+5];
int prvn;
int n;
int p[mxn+5],cnt[mxn+5],c[mxn+5];
int pn[mxn+5],cn[mxn+5];
inline void read() {
    scanf("%d %s",&n,s);
}
inline void buildsuffixArray() {
    memset (cnt, 0, alphabet * sizeof(int));
    for (int i=0; i<n; ++i) {
        ++cnt[s[i]];
    }
    for (int i=1; i<alphabet; ++i) {
        cnt[i] += cnt[i-1];
    }
    for (int i=0; i<n; ++i) {
        p[--cnt[s[i]]] = i;
    }
    c[p[0]] = 0;
    int classes = 1;
    for (int i=1; i<n; ++i) {
        if (s[p[i]] != s[p[i-1]]) {
            ++classes;
        }
        c[p[i]] = classes-1;
    }
    for (int h=0; (1<<h)<n; ++h) {
        for (int i=0; i<n; ++i) {
            pn[i] = p[i] - (1<<h);
            if (pn[i] < 0) {
                pn[i] += n;
            }
        }
        memset (cnt, 0, classes * sizeof(int));
        for (int i=0; i<n; ++i) {
            ++cnt[c[pn[i]]];
        }
        for (int i=1; i<classes; ++i) {
            cnt[i] += cnt[i-1];
        }

        for (int i=n-1; i>=0; --i) {
            p[--cnt[c[pn[i]]]] = pn[i];
        }
        cn[p[0]] = 0;
        classes = 1;
        for (int i=1; i<n; ++i) {
            int mid1 = (p[i] + (1<<h)) % n,  mid2 = (p[i-1] + (1<<h)) % n;
            if (c[p[i]] != c[p[i-1]] || c[mid1] != c[mid2]) {
                ++classes;
            }
            cn[p[i]] = classes-1;
        }
        memcpy (c, cn, n * sizeof(int));
    }
}
inline int Result(){
	int bst=0;
	for(int i=1;i<n;++i){
		if( n-p[i] >prvn ){
			while( i<n && n-p[i]>prvn){
				if( p[i]<p[bst] && p[i]){
					bst=i;
					//debug("result : ",bst, p[bst]);
				}
				++i;
			}
			break;
		}
	}		
	return p[bst]==prvn ? 0 : p[bst];
}
inline void print() {
    cout<<n<<" "<<s<<"\n";
}
inline void Make() {
    int i=n,j=0;
    for( ; j<n; ++j,++i) {
        s[i] = s[j];
    }
    prvn=n;
    n=i;
    s[n++]=0;
}
inline void Clear() {
    memset( &s[0],0,sizeof(s[0]));
}
}
/*
	double the string
	find suffix array
	result 
		- smallest index from 0 to string length
		  for which current_string-len - p[i] >= initial_string_length
*/
inline void Proc() {
    suffixArray::Make();
    //suffixArray::print();
    suffixArray::buildsuffixArray();
    cout<<suffixArray::Result();
    line;
    suffixArray::Clear();
}

//#define KASE
int main() {
    int tt;
    CI(tt);
    foE(i,1,tt) {
        suffixArray::read();
#ifdef KASE
        cout<<"Case "<<i<<": ";
#endif

        Proc();
    }


    return 0;
}